﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdbool.h>
/*
* 题目：有效的括号
* 内容：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
* 有效字符串需满足：
* 左括号必须用相同类型的右括号闭合。
* 左括号必须以正确的顺序闭合。
* 
* 链接：https://leetcode-cn.com/problems/valid-parentheses
* 
*/
/*
* 思路：
* 先实现一个数组栈，以及对应的入栈、出栈、栈顶、栈的元素个数、是否为空等功能
* 首先定义一个数组栈，对其初始化。
* 然后对输入的字符串一一进行判断，如果是左括号，入栈，如果是右括号，那么将栈顶元素取出来与之比较
* 如果匹配，在继续比较下一个字符串中的元素
* 如果不匹配，销毁数组栈，跳出循环，返回false
*/
typedef char STDataType;

typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;
}ST;

// 数组栈初始化
void StackInit(ST* ps);
// 数组栈入栈
void StackPush(ST* ps, STDataType x);
// 数组栈出栈
void StackPop(ST* ps);
// 数组栈 获得栈顶元素
STDataType StackTop(ST* ps);
// 数组栈 获得栈有效元素的个数
int StackSize(ST* ps);
// 数组栈 判断数组栈是否为空
bool StackEmpty(ST* ps);
// 数组栈销毁
void StackDestroy(ST* ps);

// 数组栈初始化
void StackInit(ST* ps)
{
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}
// 数组栈入栈
void StackPush(ST* ps, STDataType x)
{
    assert(ps);
    // 判断容量是否充足
    if (ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}
// 数组栈出栈
void StackPop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));

    ps->top--;
}
// 数组栈 获得栈顶元素
STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));

    return ps->a[ps->top - 1];
}
// 数组栈 获得栈有效元素的个数
int StackSize(ST* ps)
{
    assert(ps);

    return ps->top;
}
// 数组栈 判断数组栈是否为空
bool StackEmpty(ST* ps)
{
    return ps->top == 0;
}
// 数组栈销毁
void StackDestroy(ST* ps)
{
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

bool isValid(char* s) {
    ST st;
    StackInit(&st);
    while (*s)
    {
        if ((*s == '(') || (*s == '[') || (*s == '{'))
        {
            StackPush(&st, *s);
            s++;
        }
        else
        {
            if (StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            char ch = StackTop(&st);
            StackPop(&st);
            if ((ch == '(' && *s == ')') || (ch == '[' && *s == ']') || (ch == '{' && *s == '}'))
            {
                s++;
            }
            else
            {
                StackDestroy(&st);
                return false;
            }
        }
    }
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}